题目分析

本题难度较大，不容易想到。一开始我想的是dp，从某一个位置i开始，找后面相同字符的位置j，那么在[i, j]区间中，回文子序列长度为5的个数等于[i + 1, j - 1]区间中，回文子序列长度为3的个数。因此可以先找长度为3的回文子序列个数，这样的时间复杂度是$ O(n^2) $，无法满足本题的范围。

模拟

我们发现长度为3的回文子序列个数，因为中间的一个字符x一定是满足条件的，所以就是找x左边0的个数l，x右边0的个数r，那么0x0的数量一定是l x r，同理，1的个数，2的个数…，一直到9的个数。

那么长度为5的回文子序列个数，就是找左边00的个数l，右边00的个数r，那么00x00的数量一定是l x r，同理，01，02，… 99的个数全部加起来就是abxba的长度。

遍历每一个位置，都找左边的ab和右边的ba即可。这有一个小技巧，可以在O(n)的时间复杂度内完成，记pre1[i]数组长度为10，pre1[i]表示当前元素左边值为i的元素数量，记pre2[i]数组长度为100，pre2[i]表示当前元素左边值为i的元素数量。

那么pre1[4]表示当前元素左边3出现的数量，pre2[45]表示当前元素左边45出现的数量。可以递推得到，如果当前元素是5，那么pre2[05] += pre1[0]，pre2[15] += pre1[1]，pre2[25] += pre1[2]…

每一个字符都要考虑左边可能出现的10种情况，右边同理。

算法的时间复杂度为O(n)，空间复杂度为O(1)。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countPalindromes(String s) {
        int n = s.length();
        long[] suf = new long[10];
        long[] suf2 = new long[100];
        for (int i = n - 1; i >= 0; i--) {
            int cur = s.charAt(i) - '0';
            for (int j = 0; j < 10; j++) {
                suf2[cur * 10 + j] += suf[j];
            }
            suf[cur]++;
        }
        long[] pre = new long[10];
        long[] pre2 = new long[100];
        long res = 0;
        for (int i = 0; i < n; i++) {
            int cur = s.charAt(i) - '0';
            suf[cur]--;
            for (int j = 0; j < 10; j++) {
                suf2[cur * 10 + j] -= suf[j];
            }
            for (int j = 0; j < 100; j++) {
                res += pre2[j] * suf2[j];
            }
            for (int j = 0; j < 10; j++) {
                pre2[cur * 10 + j] += pre[j];
            }
            pre[cur]++;
        }
        return (int) (res % MOD);
    }
}

刷题总结

本题难度较大，是leetcode第92场双周赛的最后一题，小伙伴们多多学习，多刷一刷竞赛题，提升会更加迅速。